package Recursion;

import Stack.ArrayStack;

/**
 * @author yyq
 * @create 2021-10-12 21:56
 * 解决八皇后问题
 * 1 用一维数组表示棋盘
 * 2 判断judge(int n) 0->n之前的应该满足规则
 * 3 成功后打印结果
 * 4 主程序 思考用栈解决
 *
 */
public class Queue8 {
    int QueueNum=8;
    int count=0;
    //1 一维数组 arr[i]=n  i表示第几行 n表示第几列
    public int[] arr=new int[QueueNum];

    //2 满足规则
    public Boolean judge(int n){
        //满足不同行(默认满足) 不同列 不同斜线
        for (int i = 0; i < n; i++) {
            if(arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }


    //3 打印结果
    public void printQue(){
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"");
        }
        System.out.println();

    }


    //3 实现 放置第n层的皇后
    public void check(int n){
        if(n==QueueNum){ //结束递归条件 放置到第8层
            printQue(); //输出结果
            return;
        }
        for (int i = 0; i < QueueNum; i++) { //递归回溯
            arr[n]=i;   //在第n层放置到第i个位置
            if(judge(n)){ //判断第n层之前是否都可以
                check(n+1); //继续放置
            }
        }

    }

    public static void main(String[] args) {
        Queue8 queue8=new Queue8();
        queue8.check(0);
        System.out.println(queue8.count);
    }


}
